package algocasts;

public class P103_MinWindowSubstring {
    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0) return "";
        int[] required = new int[256];
        int start = 0, len = Integer.MAX_VALUE, count = t.length();
        int left = 0, right = 0;
        for (int i = 0; i < t.length(); i++)
            ++required[t.charAt(i)];
        for (; right < s.length(); ++right) {
            char r = s.charAt(right);
            if (required[r] > 0) --count;
            --required[r];

            while (count == 0) {
                if (right - left + 1 < len) {
                    start = left;
                    len = right - left + 1;
                }
                char l = s.charAt(left);
                ++required[l];
                if (required[l] > 0) count++;
                ++left;
            }

        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}
